package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
 * <p>
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * <p>
 * 必须 原地 修改，只允许使用额外常数空间。
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 视频题解：https://www.bilibili.com/video/BV1SK4y1V7ch?from=search&seid=9728306007428938581&spm_id_from=333.337.0.0
 * @version 1.0
 * @date 2021/12/17 21:20
 * 二刷，面试题
 */
public class nextPermutation {
    public static void main(String[] args) {
        // int[] nums = {4, 2, 3, 3, 1};
        int[] nums = {1,3,2};
        nextPermutation(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    // 1,2,2,1 如果我们想找1221的 nextPermutation，肯定是要将 首位1换成2，因为221 是 [2,2,1]中最大的数字
    // 首位是2后，后面的 [1,2,1] 如何排序，肯定是排成最小数
    //
    // 如何找到下一个 更大的排列：42331
    // 1. 因为下一个排列是更大的整数，所以要尽可能的动低位的数字
    // 2. 从后向前 一直单调递增的话，也就是从前往后单调递减，数组如果是单调递减的话，是没有nextPermutation(需倒序数组)
    // 所以如果找到 从后往前 第一次出现 不是单调递增的数字，就说明有 nextPermutation 存在。
    // 42331 变成 43 321, 321 倒序变成 43 123

    static void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n == 1) return;
        // 从后向前单调递增的 最后一个下标， 如：[4,2,3,3,1] last 倒数第二个3的 下标
        int last = n - 1;
        // 是否存在下一个更大排列
        boolean exist = false;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] >= nums[last]) {
                last = i;
            } else {
                exist = true;
                // 交换位置 nums[i] 与 从后向前中第一个比 nums[i] 大的元素
                swap(nums, i);
                // nums[i+1] 到 nums[n-1] 倒序
                reverseNums(nums, i + 1);
                break;
            }
        }
        // 数组是单调递减的话，特殊处理 21 ==> 12 210 ==> 012
        if (!exist){
            reverseNums(nums, 0);
        }
    }

    static void swap(int[] nums, int index){
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] > nums[index]) {
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                break;
            }
        }
    }

    // 倒序 43 321 ==> 43 123
    static void reverseNums(int[] nums, int index) {
        int left = index;
        int right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}
